import heapq
import random
from collections import defaultdict

nums = 1000
p = 0.999


class Ticket:
    def __init__(self):
        self.to = []
        self.fee = []
        self.t1 = []
        self.t2 = []


# 数据生成
e = 0
tickets = [Ticket() for _ in range(nums)]
for i in range(nums):
    ticket = tickets[i]
    while random.random() < p:
        ticket.to.append(random.randint(0, nums - 1))
        ticket.fee.append(random.randint(1, 100))
        ticket.t1.append(random.randint(1, 100))
        ticket.t2.append(random.randint(1, 100) + ticket.t1[-1])
        e += 1
print("数据生成完毕边数:", e)
heap = [(0, 0, 0)]  # (费用，时间，点)
inf = float('inf')
minist = [defaultdict(lambda: inf) for _ in range(nums)]
while heap:
    fee, t, node = heapq.heappop(heap)
    if minist[node][t] <= fee: continue
    minist[node][t] = fee
    for j in range(len(tickets[node].to)):
        to = tickets[node].to[j]
        cost = tickets[node].fee[j]
        t1 = tickets[node].t1[j]
        t2 = tickets[node].t2[j]
        if t1 < t: continue
        if fee + cost >= minist[to][t2]: continue
        heapq.heappush(heap, (fee + cost, t2, to))

for val in minist:
    mv = inf
    time = inf
    for t, v in val.items():
        if v < mv:
            mv = v
            time = t
    print(f"达到时刻 {time} cost: {mv}")
